package 零钱兑换II;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/10 13:58
 * @description:
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 * 示例 1:
 * 输入: amount = 5, coins = [1, 2, 5]
 * 输出: 4
 * 解释: 有四种方式可以凑成总金额:
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 */
public class Solution {
    public int change(int amount, int[] coins) {
        // 完全背包问题
        // ① dp数组及其含义：dp[i][j]表示金额为j时，从coins的0-i中选择硬币，选取方案的最大值
        // ② 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];
        //                      最大方案数 = 不包含coins[i]的最大方案数 + 包含coins[i]的最大方案数
        // ③ dp数组初始化：第一行根据coins[0]的面额，将面额值和coins[0]值倍数相等的dp设置为1。第一列设置为1(容量为0有一种不装物品的方案)
        // ④ 遍历顺序：先遍历coins，再遍历amount
        // ⑤ 举例推导dp数组：amount = 5, coins = [1, 2, 5]
        //              index:      0   1   2   3   4   5
        //                          1   1   1   1   1   1
        //                          1   1   2   2   3   3
        //                          1   1   2   2   3   4

        int[][] dp = new int[coins.length][amount + 1];
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = coins[0]; i <= amount; i += coins[0]) {
            dp[0][i] = 1;
        }
        print(dp);

        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            print(dp);
        }

        return dp[coins.length - 1][amount];
    }

    private void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("------------");
    }
}
